#include <stdio.h>
#include "rsa.h"

/**
 * @brief Calculate the correct index for the circulary array
 *
 * @param i Index of the array, can be negative
 *
 * @return Correct positive index.
 */
static unsigned int    calc_index(int i)
{
    switch (i)
        {
        case -1:
            return (2);
        case -2:
            return (1);
        default :
            return (i);
        }
}

/**
 * @brief Check that the multiplicative inverse of (a % b) exists.
 *
 * The multiplicative inverse of (a % b) exists only if a and b are coprime.
 * We need to check if gdc(a, b) == 1
 *
 * @param a First parameter
 * @param b Second parameter
 *
 * @return 1 if the inverse exist, 0 otherwise
 *
 */
static unsigned int     check_inverse_exsits(t_uint64 a, t_uint64 b)
{
    /* First we check that the multipicative inverse exists. */
    if (gcd(a, b) != 1)
        {
            fprintf(stderr,
                    "Multiplicative inverse does not exist, "
                    "gcd(%lu, %lu) != 1 (%lu)\n",
                    a, b, gcd(a, b));
            return (0);
        }
    return (1);
}

/**
 * @brief Verify that the inverse is correct.
 *
 * The multiplicative inverse must verify the equation (a * inverse) % b == 1
 * If the inverse is negative, we add b to it and we check the equation.
 *
 * @param a First param
 * @param b Second param
 * @param Multiplicative inverse of a % b
 *
 * @return The multiplicative inverse if it is correct, 0 ortherwise.
 */
static unsigned int     check_inverse_correct(t_uint64 a, t_uint64 b,
                                              t_int64 inverse)
{
    /* Verify the equation */
    if ((a * inverse) % b == 1)
        {
            return (inverse);
        }
    /* case where inverse < 0 */
    else if ((a * (inverse + b)) % b == 1)
        {
            return (inverse + b);
        }
    else
        {
            fprintf(stderr, "No inverse found for %lu %% %lu\n", a, b);
            return (0);
        }
}

/**
 * @brief Compute the multiplicative inverse of a % b.
 *
 * In order for the multiplicative of a % b to exists, a and b must be coprimes.
 * The mutiplicative 'd' inverse must verify the equation (d * a) % b = 1.
 * We use the extended euclidean algorithm to resolve the equation.
 *
 * @param a First param of the expression
 * @param b Second param of the expression
 *
 * @return Multiplicative inverse of a % b
 */
t_uint64       multiplicative_mod_inverse(t_uint64 a, t_uint64 b)
{
    t_uint64   r[3];
    t_int64    aux[3];
    t_uint64   q;
    t_uint64   i;

    if (check_inverse_exsits(a, b) == 0)
        return (0);
    /* Init the two first steps */
    r[0] = b;
    r[1] = a;
    aux[0] = 0;
    aux[1] = 1;
    /* Start the loop from the second step */
    i = 1;
    while (r[i] > 1)
        {
            /* As we do not infinte array and we just nede 3 values,
               we circle with % 3 */
            i = (i + 1) % 3;
            r[i] = r[calc_index(i - 2)] % r[calc_index(i - 1)];
            q = r[calc_index(i - 2)] / r[calc_index(i - 1)];
            aux[i] = -q * aux[calc_index(i - 1)] + aux[calc_index(i - 2)];
        }
    return (check_inverse_correct(a, b, aux[i]));
}
